package club.xiaojiawei.back;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/23/22 10:12 PM
 * @question 51. N 皇后
 * @description n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
public class SolveNQueens51 {

    public static void main(String[] args) {
        System.out.println(Integer.toBinaryString(-4));
        System.out.println(Integer.toBinaryString(4));
        System.out.println(-4 & 4);
        System.out.println(Integer.toBinaryString(-3));
        System.out.println(Integer.toBinaryString(3));
        System.out.println(-3 & 3);
        SolveNQueens51 test = new SolveNQueens51();
        List<List<String>> result = test.solveNQueens(4);
        System.out.println(result);
    }

    /**
     * 递归回溯
     * 时间复杂度O(n!)
     * 空间复杂度O(n)
     * @param n
     */
    public List<List<String>> solveNQueens(int n) {
        this.checkerboard = new int[n];
        this.amount = n;
        this.positions = new char[amount];
        Arrays.fill(positions, '.');
        recursion(0);
        return result;
    }

    List<List<String>> result = new ArrayList<>();

    /**
     * 下标表示行，值表示列，
     */
    int[] checkerboard;

    /**
     * 皇后数
     */
    int amount = 0;

    char[] positions;

    ArrayList<String> temp = new ArrayList<>();

    public void recursion(int nowRow){
        if (nowRow == amount){
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int col = 0; col < amount; col++) {
            checkerboard[nowRow] = col;
            if (judge(nowRow)){
                positions[col] = 'Q';
                temp.add(new String(positions));
                positions[col] = '.';
                recursion(nowRow + 1);
                temp.remove(temp.size() - 1);
            }
        }
    }

    public boolean judge(int nowRow){
        for (int oldRow = 0; oldRow < nowRow; oldRow++) {
//            检查之前的每一行，查看是否有列相同的或者处于同一斜线上的
            if (checkerboard[oldRow] == checkerboard[nowRow] || Math.abs(nowRow - oldRow) == Math.abs(checkerboard[nowRow] - checkerboard[oldRow])){
                return false;
            }
        }
        return true;
    }

    /**
     * 基于位运算的回溯（nb）
     * 时间复杂度O(n!)
     * 空间复杂度O(n)
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens2(int n) {
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        List<List<String>> solutions = new ArrayList<List<String>>();
        solve(solutions, queens, n, 0, 0, 0, 0);
        return solutions;
    }

    public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
//            availablePositions二进制表示中，所有的1表示能放皇后的位置，依次遍历这些1
            while (availablePositions != 0) {
//                取availablePositions二进制中最右边的 1 再组成二进制数，相当于 availablePositions &（~availablePositions +1）
                int position = availablePositions & (-availablePositions);
//                把最低位的1置0
                availablePositions = availablePositions & (availablePositions - 1);
//                Integer.bitCount() 计算二进制中1的个数，1的个数每遍历一次就减少一个，所有可以1的数量当作列
                int column = Integer.bitCount(position - 1);
                queens[row] = column;
//                columns | position表示更新columns,将columns二进制里对应position二进制里的1的位置处变成1,表示此列有皇后了；(diagonals1 | position) << 1, (diagonals2 | position) >> 1也类似
                solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
//                queens[row] = -1;
            }
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

}
